package map_set.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yuisama
 * @version 1.0.0
 * @Description TODO
 * @createTime 2023年04月04日 21:31:00
 */
public class Num138_CopyRandomList {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        Map<Node,Node> nodesMap = new HashMap<>();
        // 遍历原链表，构建新链表，保存在Map接口中
        Node temp = head;
        while (temp != null) {
            Node node =  new Node(temp.val);
            nodesMap.put(temp,node);
            temp = temp.next;
        }
        // 再遍历每个节点，构建新链表的next和random引用
        temp = head;
        while (temp != null) {
            nodesMap.get(temp).next = nodesMap.get(temp.next);
            nodesMap.get(temp).random = nodesMap.get(temp.random);
            temp = temp.next;
        }
        return nodesMap.get(head);
    }
}
